package warm100;

import java.util.*;

public class dailyTemperatures_793 {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        //单调栈，想法是，从右向左，保证中栈顶到栈尾单调递增
        Deque<Integer> q = new LinkedList<>();
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            while (!q.isEmpty() && temperatures[i] >= temperatures[q.peek()])   //栈顶小于当前元素
                q.poll();
            if (!q.isEmpty())   //如果为空，说明右边没有比自己更大的，不处理，数组默认就是0
                res[i] = q.peek()-i;
            q.push(i);
        }
        return res;
    }
}
